`:top

Als `!unendlichen Graph`! bezeichnet man in der `F33f`_`[Graphentheorie`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graphentheorie]`_`f einen `F33f`_`[Graphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graph_(Graphentheorie)]`_`f, dessen Knoten- oder Kantenzahl unendlich ist. Spricht man hingegen von einem `*Graphen`* so wird oft angenommen, dass Knoten- und Kantenzahl endlich sind. Ein Graph wird als `!wegendlich`! bezeichnet, falls er, trotz möglicherweise unendlich vieler Knoten, keinen unendlich langen `F33f`_`[Weg`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Weg_(Graphentheorie)]`_`f besitzt.

Aussagen über unendliche Graphen lassen sich häufig mittels eines `F33f`_`[Kompaktheitsarguments`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kompaktheitssatz_(Logik)]`_`f aus entsprechenden Aussagen über endliche Graphen ableiten. Beispielsweise ist jeder unendliche planare Graph `F33f`_`[vierfärbbar`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Vier-Farben-Satz]`_`f, weil dies für jeden endlichen planaren Graphen gilt. Dies beruht auf dem `F33f`_`[Lemma von König`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Lemma_von_König]`_`f.

Andere Aussagen sind nicht zwangsläufig auf unendliche Graphen übertragbar.

>>Contents

• `F0af`_`[Beispiele`#beispiele]`_`f

• `F0af`_`[Lokal endliche Graphen`#lokal-endliche-graphen]`_`f

• `F0af`_`[Feine Graphen`#feine-graphen]`_`f

• `F0af`_`[Anwendung`#anwendung]`_`f

• `F0af`_`[Sätze`#s-tze]`_`f

• `F0af`_`[Literatur`#literatur]`_`f

• `F0af`_`[Einzelnachweise`#einzelnachweise]`_`f

-─

>>Beispiele

`F33f`_`[Cayley-Graphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Cayley-Graph]`_`f unendlicher Gruppen Γ Γ {\\displaystyle \\Gamma } sind Beispiele unendlicher Graphen mit sehr hoher Symmetrie. (Alle Elemente der Gruppe Γ Γ {\\displaystyle \\Gamma } sind Symmetrien des Graphen.)

In vielen inner- und außermathematischen Anwendungen sind `F33f`_`[Expander-Graphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Expander-Graph]`_`f von Bedeutung.

>>Lokal endliche Graphen

Ein Graph heißt `*lokal endlich`*, wenn jeder Knoten nur endlich viele Nachbarn hat.

>>Feine Graphen

Eine in der `F33f`_`[geometrischen Gruppentheorie`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Geometrische_Gruppentheorie]`_`f wichtige Klasse von Graphen sind `F33f`_`[feine Graphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Feiner_Graph]`_`f, sie umfassen lokal endliche Graphen und zum Beispiel den `F33f`_`[Farey-Graph`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Farey-Graph]`_`f.

>>Anwendung

In der `F33f`_`[Funktionalanalysis`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Funktionalanalysis]`_`f treten unendliche Graphen als sogenannte `F33f`_`[Bratteli-Diagramme`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Bratteli-Diagramm]`_`f bei der Untersuchung von `F33f`_`[AF-C*-Algebren`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=AF-C*-Algebra]`_`f auf.

>>Sätze

Zu den Sätzen über endliche Graphen, die Erweiterungen auf unendliche Graphen haben, gehören:

• der `F33f`_`[Heiratssatz`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Heiratssatz]`_`f von `F33f`_`[Philip Hall`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Philip_Hall]`_`f, bewiesen von `F33f`_`[Ron Aharoni`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Ron_Aharoni]`_`f, Crispin Nash-Williams und `F33f`_`[Saharon Shelah`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Saharon_Shelah]`_`f.`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f]`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f]`:cite-ref-3[`F5bf`_`[3`#cite-note-3]`_`f] Ebenso auf den unendlichen Fall übertragbar sind die Verallgemeinerung des Heiratssatzes von Richard Rado und der `F33f`_`[Satz von Dilworth`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Satz_von_Dilworth]`_`f.

• Der `F33f`_`[Satz von König`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Satz_von_König_(Graphentheorie)]`_`f, wie schon `F33f`_`[Paul Erdős`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Paul_Erdős]`_`f vermutete und wie Aharoni bewies.`:cite-ref-4[`F5bf`_`[4`#cite-note-4]`_`f]`:cite-ref-5[`F5bf`_`[5`#cite-note-5]`_`f]

• der `F33f`_`[Satz von Menger`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Satz_von_Menger]`_`f, bewiesen von Aharoni und Eli Berger.`:cite-ref-6[`F5bf`_`[6`#cite-note-6]`_`f]

>>Literatur

• `F33f`_`[Dénes Kőnig`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Dénes_Kőnig]`_`f: `*Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe`*, Akademische Verlagsgesellschaft, Leipzig 1936

• `F33f`_`[Reinhard Diestel`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Reinhard_Diestel]`_`f: `*Infinite graphs`*, Kapitel 8 in Reinhard Diestel: `*Graph theory. 4th [electronic] edition 2010. Corrected reprint 2012`*, Springer, 2012, ISBN 978-3-642-14278-9, S. 203–268 (englisch; Inhaltsverzeichnis)

>>Einzelnachweise

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah,. Marriage in infinite societies, in: Progress in Graph Theory (Waterloo, Ontario, 1982), Academic Press, Toronto, 1984, S. 71–79

`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah, A general criterion for the existence of transversals, Proceedings of the London Mathematical Society, Band 3, 1983, S. 43–68.

`:cite-note-3`!3.`! `F0af`_`[↑`#cite-ref-3]`_`f R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah, Another Form of a Criterion for the Existence of Transversals, Journal of the London Mathematical Society, Band 2, 1984, S. 193–203

`:cite-note-4`!4.`! `F0af`_`[↑`#cite-ref-4]`_`f Aharoni, König's duality theorem for infinite bipartite graphs, Journal of the London Mathematical Society, Band 2, 1984, S. 1–12

`:cite-note-5`!5.`! `F0af`_`[↑`#cite-ref-5]`_`f Aharoni, On a duality principle in infinite bipartite graphs, Journal of the London Mathematical Society, Band 2, 1983, S. 385–392

`:cite-note-6`!6.`! `F0af`_`[↑`#cite-ref-6]`_`f R. Aharoni, E. Berger, Menger’s theorem for infinite graphs, Inventiones Mathematicae, Band 176, 2009, S. 1–62

`c`F0af`_`[↑ Back to top`#top]`_`f`a